home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group01b.txt / 000046_icon-group-sender_Tue Mar 6 08:17:26 2001.msg < prev    next >
Internet Message Format  |  2002-01-03  |  3KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id f26FFok03729
  4.     for icon-group-addresses; Tue, 6 Mar 2001 08:15:50 -0700 (MST)
  5. Message-Id: <200103061515.f26FFok03729@baskerville.CS.Arizona.EDU>
  6. Subject: Re: New Scientist puzzle
  7. Date: Mon, 5 Mar 2001 18:20:57 -0800
  8. x-sender: cary@adlmail.cup.hp.com
  9. From: Cary Coutant <cary@cup.hp.com>
  10. To: "Icon-group" <icon-group@cs.arizona.edu>
  11. Errors-To: icon-group-errors@cs.arizona.edu
  12. Status: RO
  13. Content-Length: 2621
  14.  
  15. After doing a solution in Icon, I got to thinking that this problem would 
  16. be fun to solve in APL. After dusting off my APL programming skills 
  17. (dormant for 26 years now), I wasn't able to come up with something as 
  18. elegant as I had hoped for. (Some may question the use of "elegant" in 
  19. the same sentence as "APL.")
  20.  
  21. My apologies for going so far off topic, but we've already seen a 
  22. solution in MUMPS (another language I haven't seen for 26 years), and I 
  23. thought this would be another interesting contrast to Icon.
  24.  
  25. What I wanted to do was something like this (with accomodation for the 
  26. ASCII character set):
  27.  
  28. Start with a function F that compares two numbers X and Y and returns a 
  29. boolean indicating whether they match the pattern. The trick in line [2] 
  30. is exactly the same trick I used with map() in my Icon solution.
  31.  
  32.       del R <- X F Y; NUMS
  33. [1]   NUMS <- (((rho PAT1), 0) format X), ((rho PAT2), 0) format Y
  34. [2]   R <- and / (PATS[NUMS iota NUMS]=PATS), NUMS[PATS iota PATS]=NUMS
  35.       del
  36.  
  37. The function VIER takes a vector of squares (line [4]), and forms the 
  38. outer result (line [5]) of that vector with itself, using my function F. 
  39. This would produce a matrix of booleans indicating each pair of squares 
  40. that satisfies the pattern (the first condition). In line [6], I 
  41. plus-reduce the matrix row-wise and column-wise, check for rows and 
  42. columns that have only one solution, expand those reduced vectors out 
  43. again, then and everything together to form a matrix with only a single 
  44. 1. Lines 7 and 8 print the two squares corresponding to that entry.
  45.  
  46.       del VIER; SQ; M
  47. [1]   PAT1 <- 'VIER'
  48. [2]   PAT2 <- 'NEUN'
  49. [3]   PATS <- PAT1,PAT2
  50. [4]   SQ <- (31 drop iota 99) * 2
  51. [5]   M <- SQ jot . F SQ
  52. [6]   M <- M & ((rho M) rho 1 = + bar/ M) &
  53.                transpose (reverse rho M) rho 1 = +/M
  54. [7]   (or / M) / SQ
  55. [8]   (or bar/ M) / SQ
  56.       del
  57.  
  58. Unfortunately, APL doesn't support outer result with user-defined 
  59. functions. (To me, that's like not supporting user-defined generators in 
  60. Icon!) I ended up writing a function XMATCH that produced the outer 
  61. result using traditional looping techniques.
  62.  
  63. Then I had one more problem. The version of APL I was using (CAPLIB for 
  64. DOS, running on a Mac under Virtual PC) crashed when I tried to make the 
  65. 68-by-68 result matrix. I ended up having to filter the list of squares 
  66. into two lists: VSQ containing only those squares that matched the 
  67. pattern "VIER", and NSQ containing only those squares that matched the 
  68. pattern "NEUN". With the smaller matrix to deal with, it was able to come 
  69. up with the solution.
  70.  
  71. It was a fun exercise, though!
  72.  
  73. -cary
  74.